package 面试.遍历算法;

public class 插入排序 {
    //拿到比较数一个个去和前面得数组部分比较，默认前面得数组是排序好的，升序
    public static void main(String[] args) {
        int[] arr = {7,4,3,9,6,5,3,4,21,23,52,12,86,23,34,15,25,16,867,92,82,223,123,556,234,12356,21312,643,12312,645,32421,12334,324,21,34,153,123312,42342};
        long start = System.currentTimeMillis();
        for (int i = 1; i < arr.length; i++) {
            int num = arr[i];
            int j = i-1;
            while (num < arr[j]){
                arr[j+1] = arr[j];
                j--;
                if(j < 0){
                    break;
                }

            }
            arr[j+1] = num;
        }
        long end = System.currentTimeMillis();
        System.out.println(end - start);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}
